home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / gfx / 3d / irit50src.lha / irit5 / bool_lib / bool2low.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-30  |  47.7 KB  |  1,176 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d (not only polygonal) solid modeller.             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle the low level boolean operations. The routines in this  *
  7. * module should be accessed from "bool-hi.c" module only.             *
  8. *   Note the polygons of the two given objects may not be convex, and must   *
  9. * be subdivided into convex ones in the boolean upper level routines (module *
  10. * bool-hi.c). All the routines of this module expects objects with convex    *
  11. * polygons only although they might return objects with non convex polygons, *
  12. * but marked as so (via polygons CONVEX tags - see IPPolygonStruct def.)!    *
  13. *   Because Bool-low.c module was too big, it was subdivided to two:         *
  14. * Bool1Low.c - mainly handles the intersecting polyline between the oprnds.  *
  15. * Bool2Low.c - mainly handles the polygon extraction from operands given the *
  16. *           polyline of intersection and the adjacencies (see ADJACNCY.C) *
  17. *****************************************************************************/
  18.  
  19. /* #define DEBUG        If defined, return intersection POLYLINE object. */
  20. /* #define DEBUG2             If defined, defines some printing routines. */
  21. /* #define DEBUG3             Print messages to entry/exit from routines. */
  22.  
  23. #include <stdio.h>
  24. #include <ctype.h>
  25. #include <math.h>
  26. #include <string.h>
  27. #include "irit_sm.h"
  28. #include "allocate.h"
  29. #include "bool_loc.h"
  30. #include "convex.h"
  31. #include "geomat3d.h"
  32. #include "intrnrml.h"
  33.  
  34. static IPVertexStruct *InterLoopToVrtxList(InterSegmentStruct *PIHead);
  35. static int TestAinB(IPVertexStruct *V, IPPolygonStruct *Pl, int AinB);
  36. static IPPolygonStruct *ClipOpenLoopFromPoly(IPPolygonStruct *Pl,
  37.                          InterSegListStruct *OLoop,
  38.                          int AinB);
  39. static void ClosedLoopsToPolys(InterSegListStruct *PClosed,
  40.                    IPPolygonStruct *Pl);
  41. static IPVertexStruct *GenReverseVrtxList(IPVertexStruct *VIn);
  42. static IPVertexStruct *CutPolygonAtRay(IPPolygonStruct *Pl, PointType Pt);
  43. static int CombineClosedLoops(IPPolygonStruct *Pl,
  44.                   InterSegListStruct *PClosed,
  45.                   int AinB);
  46. static void PushAdjOnStack(IPPolygonStruct *Pl,
  47.                IPPolygonStruct *AdjStack[],
  48.                int *StackPointer);
  49. static IPPolygonStruct *ChainPolyLists(IPPolygonStruct *Pl1,
  50.                        IPPolygonStruct *Pl2);
  51.  
  52. #ifdef DEBUG
  53. void BoolPrintVrtxList(IPVertexStruct *V);
  54. void BoolPrintInterList(InterSegmentStruct *PInt);
  55. #endif /* DEBUG */
  56.  
  57. /*****************************************************************************
  58. * DESCRIPTION:                                                               *
  59. * Test on which side of polygon Pl, given Point V is, and according to       *
  60. * the requirement (AinB) returns TRUE/FALSE.                     *
  61. *   If test on V fails, we tries the next one V -> Pnext until success...    *
  62. *                                                                            *
  63. * PARAMETERS:                                                                *
  64. *   V:       Is V inside/outside polygon Pl?                                 *
  65. *   Pl:      The polygon to test for inclusion.                              *
  66. *   AinB:    Either test for inclusion (TRUE) or exclusion (FALSE).          *
  67. *                                                                            *
  68. * RETURN VALUE:                                                              *
  69. *   int:     TRUE if V relates to PL as AinB, FALSE otherwise.               *
  70. *****************************************************************************/
  71. static int TestAinB(IPVertexStruct *V, IPPolygonStruct *Pl, int AinB)
  72. {
  73.     int In;
  74.     RealType Distance;
  75.     IPVertexStruct
  76.     *VHead = V;
  77.  
  78.     do {
  79.     Distance = Pl -> Plane[0] * V -> Coord[0] +
  80.            Pl -> Plane[1] * V -> Coord[1] +
  81.            Pl -> Plane[2] * V -> Coord[2] + Pl -> Plane[3];
  82.     In = Distance > 0.0;
  83.     V = V -> Pnext;
  84.     }
  85.     while (ABS(Distance) < BOOL_EPSILON && V != NULL && V != VHead);
  86.  
  87.     if (ABS(Distance) < BOOL_EPSILON)
  88.     IritFatalError("TestAInB: Failed to find non coplanar point.");
  89.  
  90.     return (In && AinB) || (!In && !AinB);   /* I wish I had logical XOR ... */
  91. }
  92.  
  93. /*****************************************************************************
  94. * DESCRIPTION:                                                               *
  95. *   Converts an intersection loop into an open vertex list.             *
  96. *                                                                            *
  97. * PARAMETERS:                                                                *
  98. *   PIHead:  Intersection list to be converted.                              *
  99. *                                                                            *
  100. * RETURN VALUE:                                                              *
  101. *   IPVertexStruct *: The same loop as a vertex list.                        *
  102. *                                                                            *
  103. * KEYWORDS:                                                                  *
  104. *   InterLoopToVrtxList                                                      *
  105. *****************************************************************************/
  106. static IPVertexStruct *InterLoopToVrtxList(InterSegmentStruct *PIHead)
  107. {
  108.     IPVertexStruct *VHead, *V;
  109.  
  110.     VHead = V = IPAllocVertex(0, 0, NULL, NULL);
  111.  
  112.     PT_COPY(VHead -> Coord, PIHead -> PtSeg[0]);
  113.  
  114.     while (PIHead != NULL) {
  115.     V -> Pnext = IPAllocVertex(0, 0, NULL, NULL);
  116.     V = V -> Pnext;
  117.     PT_COPY(V -> Coord, PIHead -> PtSeg[1]);
  118.  
  119.     PIHead = PIHead -> Pnext;
  120.     }
  121.  
  122.     V -> Pnext = NULL;
  123.  
  124.     return VHead;
  125. }
  126.  
  127. /*****************************************************************************
  128. * DESCRIPTION:                                                               *
  129. *   Clip an open loop from a polygon:                         *
  130. * 1. Clip the section (S) of the polygon between the two end points of the   *
  131. *    loop end points and replace it by the loop itself.                 *
  132. * 2. If the polygon formed from S and the loop should be in the output       *
  133. *    (as tested by AinB) returns that polygon. Otherwise returns NULL.         *
  134. *   The open loop itself (excluding the header OLoop) is freed.             *
  135. * Note it is assumed (ordered by the sorting routines above) that the open   *
  136. * loop starts from the second end back to first end:                 *
  137. *                                         *
  138. *                   L1-----------------------L2             *
  139. *                |            |             *
  140. *                |L0            |L3             *
  141. *    *---------------*-------+----*-------------*----+-----------*         *
  142. *    P0        P1         P2           P3            P0         *
  143. *                                                                            *
  144. * PARAMETERS:                                                                *
  145. *   Pl:        To clip against the given open loop.                          *
  146. *   OLoop:     The given open loop (must start/end on Pl's boundary).        *
  147. *   AinB:      TRUE for inclusion, FALSE for exclusion.                      *
  148. *                                                                            *
  149. * RETURN VALUE:                                                              *
  150. *   IPPolygonStruct: The newly created clipped polygon if AinB, or NULL      *
  151. *                    otherwise.                                              *
  152. *****************************************************************************/
  153. static IPPolygonStruct *ClipOpenLoopFromPoly(IPPolygonStruct *Pl,
  154.                          InterSegListStruct *OLoop,
  155.                          int AinB)
  156. {
  157.     int GenClipPoly;        /* TRUE if needs to form polygon from S & OLoop. */
  158.     IPVertexStruct *VStart, *VEnd, *VEnd1,    /* Corresponds to L0 and L3... */
  159.     *ClipPoly,            /* The clipped element from polygon. */
  160.     *PLoop,                  /* The loop itself as vertex list. */
  161.     *PLoopEnd, *PLoopEnd1, *Ptemp1, *Ptemp2,
  162.     *PRevLoop = NULL;
  163.     InterSegmentStruct *PISeg, *PItemp;
  164.     IPPolygonStruct *ClipPl;
  165.  
  166. #ifdef DEBUG3
  167.     printf("Enter ClipOpenLoopFromPoly\n");
  168. #endif /* DEBUG3 */
  169.  
  170.     PISeg = OLoop -> PISeg;
  171.     VStart = PISeg -> V[0];
  172.     while (PISeg -> Pnext != NULL) PISeg = PISeg -> Pnext;
  173.     VEnd = PISeg -> V[1];
  174.     if (VStart == NULL || VEnd == NULL)
  175.     IritFatalError("ClipOpenLoopFromPoly: None open loop");
  176.     VEnd1 = VEnd;           /* Find the pointer thats points on VEnd. */
  177.     while (VEnd1 -> Pnext != VEnd) VEnd1 = VEnd1 -> Pnext;
  178.  
  179.     PLoop = InterLoopToVrtxList(OLoop -> PISeg);/* Make vertex list out of it*/
  180.     PLoopEnd = PLoop;              /* Prepare pointer on last vertex. */
  181.     while (PLoopEnd -> Pnext != NULL) PLoopEnd = PLoopEnd -> Pnext;
  182.     PLoopEnd1 = PLoop;
  183.     while (PLoopEnd1 -> Pnext != PLoopEnd) PLoopEnd1 = PLoopEnd1 -> Pnext;
  184.  
  185.     if (VStart != VEnd) {
  186.     /* Now we test if we need to create a polygon formed from S & open   */
  187.     /* loop by testing on which side of the polygon that caused         */
  188.     /* intersection L0L1, point P2 is, and compare with requirement AinB.*/
  189.     GenClipPoly = TestAinB(VStart -> Pnext, OLoop -> PISeg -> Pl, AinB);
  190.  
  191.     /* Keep the clipped VertexList P2, P3 & substitute with open loop:   */
  192.     /* Note we must keep vertex VEnd in the polygon as another InterSeg. */
  193.     /* may point on it, so we replace InterSeg point (L3) by (P3) and    */
  194.     /* leave VEnd intact.                             */
  195.     Ptemp1 = VEnd -> Pnext;             /* Save that pointer temporary. */
  196.     VEnd -> Pnext = NULL;           /* Close the clipped vertex list. */
  197.  
  198.     PT_SWAP(VEnd -> Coord, PLoopEnd -> Coord);
  199.     PT_SWAP(VEnd -> Normal, PLoopEnd -> Normal);
  200.     VEnd1 -> Pnext = PLoopEnd;
  201.     PLoopEnd1 -> Pnext = VEnd;
  202.     PLoopEnd -> Count = VEnd -> Count;
  203.     PLoopEnd -> Tags = VEnd -> Tags;
  204.  
  205.     Ptemp2 = VEnd;
  206.     VEnd = PLoopEnd;
  207.     PLoopEnd = Ptemp2;
  208.  
  209.     ClipPoly = VStart -> Pnext;
  210.  
  211.     /* New ClipPoly is isolated (Open loop of P2, P3 only). Save         */
  212.     /* reversed list of open loop if we need to form an S/OLoop polygon, */
  213.     /* otherwise free ClipPoly. Chain the OLoop instead of S.         */
  214.     if (GenClipPoly)
  215.         PRevLoop = GenReverseVrtxList(PLoop);
  216.     else
  217.         IPFreeVertexList(ClipPoly);
  218.     VStart -> Pnext = PLoop;        /* Chain the OLoop instead of S. */
  219.     PLoopEnd -> Pnext = Ptemp1;
  220.     }
  221.     else { /* VStart == VEnd */
  222.     /* Now we test if we need to create a polygon formed from S & open   */
  223.     /* loop by testing on which side of the polygon that caused         */
  224.     /* intersection L0L1, point L3 is, and compare with requirement AinB.*/
  225.     GenClipPoly = TestAinB(PLoopEnd, OLoop -> PISeg -> Pl, AinB);
  226.  
  227.     /* In this case the clipped part is empty, so its simpler: */
  228.     ClipPoly = NULL;
  229.  
  230.     /* Save reversed list of open loop if we need to form an S/OLoop     */
  231.     /* polygon. Chain the OLoop instead of S.                 */
  232.     if (GenClipPoly)
  233.         PRevLoop = GenReverseVrtxList(PLoop);
  234.  
  235.     PLoopEnd -> Pnext = VEnd -> Pnext;
  236.     PLoopEnd -> Tags = VEnd -> Tags;
  237.     VStart -> Pnext = PLoop;        /* Chain the OLoop instead of S. */
  238.     }
  239.  
  240.     /* Time to free the InterSegment list pointed by OLoop: */
  241.     PISeg = OLoop -> PISeg;
  242.     while (PISeg != NULL) {
  243.     PItemp = PISeg;
  244.     PISeg = PISeg -> Pnext;
  245.     IritFree((VoidPtr) PItemp);
  246.     }
  247.     OLoop -> PISeg = NULL;            /* To be on the safe side... */
  248.  
  249.     /* There is a chance that Pl -> PVertex will point on vertex in clipped  */
  250.     /* part so we update it to point on VStart, which for sure is in polygon.*/
  251.     Pl -> PVertex = VStart;
  252.     if (GenClipPoly) {       /* Generate the polygon from ClipPoly & PRevLoop: */
  253.     PLoopEnd = PRevLoop;
  254.     while (PLoopEnd -> Pnext != NULL)
  255.         PLoopEnd = PLoopEnd -> Pnext;
  256.  
  257.     if (ClipPoly == NULL) {
  258.         PLoopEnd -> Pnext = PRevLoop;  /* Close that loop and return it. */
  259.         ClipPl = IPAllocPolygon(0, (ByteType) (IS_COPLANAR_POLY(Pl)),
  260.                     PRevLoop, NULL);
  261.         PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
  262.         IP_RST_CONVEX_POLY(ClipPl);           /* May be not convex now. */
  263.         return ClipPl;
  264.     }
  265.  
  266.     PLoopEnd -> Pnext = ClipPoly;
  267.     PLoopEnd -> Tags = VStart -> Tags;
  268.     PLoopEnd -> Count = VStart -> Count;
  269.     Ptemp1 = ClipPoly;
  270.     while (Ptemp1 -> Pnext != NULL) Ptemp1 = Ptemp1 -> Pnext;
  271.     Ptemp1 -> Pnext = PRevLoop;
  272.  
  273.     ClipPl = IPAllocPolygon(0, (ByteType) (IS_COPLANAR_POLY(Pl)),
  274.                 ClipPoly, NULL);
  275.     PLANE_COPY(ClipPl -> Plane, Pl -> Plane);
  276.     IP_RST_CONVEX_POLY(ClipPl);           /* May be not convex now. */
  277.     return ClipPl;
  278.     }
  279.     else
  280.     return NULL;
  281. }
  282.  
  283. /*****************************************************************************
  284. * DESCRIPTION:                                                               *
  285. *   Creates a new vertex list, in reverse order. The original list is not    *
  286. * modified.                                                                  *
  287. *                                                                            *
  288. * PARAMETERS:                                                                *
  289. *   VIn:      To create a reversed list for.                                 *
  290. *                                                                            *
  291. * RETURN VALUE:                                                              *
  292. *   IPVertexStruct *: The newly created reversed list.                       *
  293. *****************************************************************************/
  294. static IPVertexStruct *GenReverseVrtxList(IPVertexStruct *VIn)
  295. {
  296.     IPVertexStruct *VOutHead, *VOut;
  297.  
  298.     VOutHead = IPAllocVertex(0, 0, NULL, NULL);
  299.  
  300.     PT_COPY(VOutHead -> Coord, VIn -> Coord);
  301.     VIn = VIn -> Pnext;
  302.  
  303.     while (VIn != NULL) {
  304.     VOut = IPAllocVertex(0, 0, NULL, NULL);
  305.     PT_COPY(VOut -> Coord, VIn -> Coord);
  306.     PT_COPY(VOut -> Normal, VIn -> Normal);
  307.  
  308.     VOut -> Pnext = VOutHead;         /* Chain them in reverse order. */
  309.     VOutHead = VOut;
  310.  
  311.     VIn = VIn -> Pnext;
  312.     }
  313.  
  314.     return VOutHead;
  315. }
  316.  
  317. /*****************************************************************************
  318. * DESCRIPTION:                                                               *
  319. *   Finds the intersection of the ray fired from Pt to +X direction with the *
  320. * given polygon. Note Pt MUST be in the polygon. Two vertices equal to         *
  321. * ray/polygon intersection point are added to polygon vertex list, and a     *
  322. * pointer to the first one is also returned. This routine is exclusively     *
  323. * used by the CombineClosedLoops below.                         *
  324. *   The polygon is NOT assumed to be convex and we look for the minimum X    *
  325. * intersection. The polygon might not be convex as a result of combinning    *
  326. * some other closed loop before we got to do this test.                 *
  327. *                                                                            *
  328. * PARAMETERS:                                                                *
  329. *   Pl:     The polygon to compute the ray intersection with.                *
  330. *   Pt:     The origin of the ray point.                                     *
  331. *                                                                            *
  332. * RETURN VALUE:                                                              *
  333. *   IPVertexStruct *:  The added vertex on Pl where the intersection with    *
  334. *                      the ray occured.                                      *
  335. *****************************************************************************/
  336. static IPVertexStruct *CutPolygonAtRay(IPPolygonStruct *Pl, PointType Pt)
  337. {
  338.     int OnVertex = FALSE;
  339.     RealType X,
  340.     MinX = INFINITY;
  341.     IPVertexStruct *V, *Vnext,
  342.     *VMinX = NULL;
  343.  
  344.     V = Pl -> PVertex;
  345.     do {
  346.     Vnext = V -> Pnext;
  347.  
  348.     /* A polygon edge might intersect the ray iff one of the following:  */
  349.     /* 1. The first vertex is exactly on the ray Y level. (if this is    */
  350.     /*    true for the second edge, it will be detected next iteration). */
  351.     /* 2. The first vertex is below ray Y level, and second is above.    */
  352.     /* 3. The first vertex is above ray Y level, and second is below.    */
  353.     if (BOOL_APX_EQ(V -> Coord[1], Pt[1])) {        /* Case 1 above. */
  354.         if (MinX > V -> Coord[0] && Pt[0] < V -> Coord[0]) {
  355.         OnVertex = TRUE;
  356.         MinX = V -> Coord[0];
  357.         VMinX = V;
  358.         }
  359.     }
  360.     else if ((V -> Coord[1] < Pt[1] &&
  361.           Vnext -> Coord[1] > Pt[1]) || /* Case 2. */
  362.          (V -> Coord[1] > Pt[1] &&
  363.           Vnext -> Coord[1] < Pt[1])) { /* Case 3. */
  364.         X = ((Vnext -> Coord[1] - Pt[1]) * V -> Coord[0] +
  365.          (Pt[1] - V -> Coord[1]) * Vnext -> Coord[0]) /
  366.         (Vnext -> Coord[1] - V -> Coord[1]);
  367.         if (MinX > X && Pt[0] < X) {
  368.         OnVertex = FALSE;
  369.         MinX = X;
  370.         VMinX = V;
  371.         }
  372.  
  373.     }
  374.  
  375.     V = Vnext;
  376.     }
  377.     while (V != NULL && V != Pl -> PVertex);
  378.  
  379.     if ((V = VMinX) == NULL)
  380.     IritFatalError("CutPolygonAtRay: fail to find intersection");
  381.  
  382.     /* Now that we have the intersection point - create two new vertices     */
  383.     /* (one if OnVertex), insert them (it) after V and return the first.     */
  384.     if (OnVertex) {
  385.     V -> Pnext = IPAllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
  386.     PT_COPY(V -> Pnext -> Coord, V -> Coord);
  387.     PT_CLEAR(V -> Pnext -> Normal);
  388.     V -> Tags = V -> Count = 0;
  389.     }
  390.     else {
  391.     V -> Pnext = IPAllocVertex(V -> Count, V -> Tags, NULL, V -> Pnext);
  392.     Vnext = V -> Pnext;
  393.     Vnext -> Coord[0] = MinX;     /* X - as intersection point found. */
  394.     Vnext -> Coord[1] = Pt[1];          /* Y - must be as ray Y level. */
  395.     Vnext -> Coord[2] = V -> Coord[2];/* Z - all polys has same Z value. */
  396.  
  397.     V -> Pnext = IPAllocVertex(0, 0, NULL, V -> Pnext);
  398.     V = V -> Pnext;
  399.     PT_COPY(V -> Coord, Vnext -> Coord);
  400.     PT_CLEAR(V -> Normal);
  401.     }
  402.  
  403.     return V;
  404. }
  405.  
  406. /*****************************************************************************
  407. * DESCRIPTION:                                                               *
  408. *   Converts the given closed loop list to polygons, and returns them. The   *
  409. * original given polygon's vertex list is freed, and the first loop is       *
  410. * substituted instead.                                 *
  411. *                                                                            *
  412. * PARAMETERS:                                                                *
  413. *   PClosed:   To substitute into polygon Pl.                                *
  414. *   Pl:        Polygon whose vertices are to be replaced by PClosed loops.   *
  415. *                                                                            *
  416. * RETURN VALUE:                                                              *
  417. *   void                                                                     *
  418. *****************************************************************************/
  419. static void ClosedLoopsToPolys(InterSegListStruct *PClosed,
  420.                    IPPolygonStruct *Pl)
  421. {
  422.     int LoopNum = 0;
  423.     IPVertexStruct *V, *VHead;
  424.     InterSegmentStruct *PISeg, *PItemp;
  425.     InterSegListStruct *PClosedTemp;
  426.  
  427.     IPFreeVertexList(Pl -> PVertex);
  428.  
  429.     SET_INOUTPUT_POLY(Pl);           /* Mark the polygon as in output. */
  430.  
  431.     while (PClosed != NULL) {
  432.     /* Convert the InterList to vertex list and free the first: */
  433.     V = VHead = InterLoopToVrtxList(PClosed -> PISeg);
  434.     if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
  435.         IritFatalError("ClosedLoopsToPolys: Closed loop with less than 3 vertices");
  436.  
  437.     PISeg = PClosed -> PISeg;      /* Time to free the InterSegmentList: */
  438.     while (PISeg != NULL) {
  439.         PItemp = PISeg;
  440.         PISeg = PISeg -> Pnext;
  441.         IritFree((VoidPtr) PItemp);
  442.     }
  443.  
  444.     while (V -> Pnext -> Pnext != NULL)
  445.         V = V -> Pnext;                   /* Go to last pt. */
  446.     IPFreeVertex(V -> Pnext);        /* and free - same as first. */
  447.     V -> Pnext = VHead;               /* Make vertex list circular. */
  448.  
  449.     if (LoopNum++) {
  450.         Pl -> Pnext = IPAllocPolygon(0, (ByteType) (IS_COPLANAR_POLY(Pl)),
  451.                      VHead, Pl -> Pnext);
  452.         PLANE_COPY(Pl -> Pnext -> Plane, Pl -> Plane);
  453.     }
  454.     else {
  455.         Pl -> PVertex = VHead;
  456.     }
  457.  
  458.     PClosedTemp = PClosed;
  459.     PClosed = PClosed -> Pnext;
  460.     IritFree((VoidPtr) PClosedTemp);
  461.     }
  462. }
  463.  
  464. /*****************************************************************************
  465. * DESCRIPTION:                                                               *
  466. *   This routines cuts the given polygon into its interior closed loops by   *
  467. * adding an edge from the polygon boundary to each of its closed loops.      *
  468. *   For example:                                 *
  469. *                                         *
  470. * +-----------------------+      +-----------------------+             *
  471. * |                       |     |                       |             *
  472. * |  / \         / \      |     |  / \________ / \      |             *
  473. * |  \ /        |   |     |     |  \ /        |   |_____|             *
  474. * |      _       \ /      | -->  |      _       \ /      |             *
  475. * |     / \_              | -->  |     / \_              |             *
  476. * |    |    |             |     |    |    |_____________|             *
  477. * |     \__/              |     |     \__/              |             *
  478. * |                       |      |                       |             *
  479. * +-----------------------+      +-----------------------+             *
  480. *                                         *
  481. *   Algorithm:                                     *
  482. * 1. Transform the polygon and the closed loops to a plane parallel to XY    *
  483. *    plane (Z = Const plane).                             *
  484. * 2. For each loop find its MaxX while keeping the information on the        *
  485. *    vertex on that extremum.                             *
  486. * 3. For the loop with the biggest MaxX:                     *
  487. *    3.1. Use that extremum vertex (which must be non concave corner) to     *
  488. *         test if loop is in the reverse direction the polygon itself is,    *
  489. *         and reverse it if not.                         *
  490. *    3.2. Fire a ray from the extremum vertex, to the +X direction outside   *
  491. *         of the loop till it intersect the polygon, break the polygon at    *
  492. *         that point and add two edges to beginning of loop from breaking    *
  493. *         point and from end of loop to breaking point (beginning/end point  *
  494. *      of loop is the extremum vertex point).                 *
  495. * 4. Repeat step 3, with all loops.                         *
  496. * 5. Transfrom the new polygon back (using the inverse matrix of step 1)     *
  497. *    to its original orientation.                         *
  498. *                                         *
  499. * PARAMETERS:                                                                *
  500. *   Pl:        Polygon to comine with the given closed loops, in place.      *
  501. *   PClosed:   Closed loops in polygon Pl.                                   *
  502. *   AinB:      Do we want inclusion or exclusion?                            *
  503. *                                                                            *
  504. * RETURN VALUE:                                                              *
  505. *   int:       TRUE iff the original polygon boundary is in output.         *
  506. *****************************************************************************/
  507. static int CombineClosedLoops(IPPolygonStruct *Pl,
  508.                   InterSegListStruct *PClosed,
  509.                   int AinB)
  510. {
  511.     RealType MaxX;
  512.     PointType V1, V2, Normal, PlNormal;
  513.     MatrixType RotMat;
  514.     IPVertexStruct *V, *Vnext, *Vprev, *VHead, *VMaxX, VStruct;
  515.     InterSegListStruct *PClosedTemp, *PClosedMaxX, *PClosedLast,
  516.     *PClosedMaxXLast = NULL;
  517.     InterSegmentStruct *PISeg, *PItemp, *PISegMaxX;
  518.  
  519.     /* Stage 1 - Transform the vertices to a plane parallel to XY plane: */
  520.     GenRotateMatrix(RotMat, Pl -> Plane);
  521.     V = VHead = Pl -> PVertex;
  522.     do {                    /* Transform the polygon itself. */
  523.     MatMultVecby4by4(V -> Coord, V -> Coord, RotMat);
  524.     V = V -> Pnext;
  525.     }
  526.     while (V != NULL && V != VHead);
  527.  
  528.     PClosedTemp = PClosed;
  529.     while (PClosedTemp != NULL) {        /* And transform the loops also. */
  530.     PISeg = PClosed -> PISeg;
  531.     while (PISeg != NULL) {
  532.         MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0], RotMat);
  533.         MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1], RotMat);
  534.  
  535.         PISeg = PISeg -> Pnext;
  536.     }
  537.  
  538.     PClosedTemp = PClosedTemp -> Pnext;
  539.     }
  540.     if (!MatInverseMatrix(RotMat, RotMat))     /* Find the inverse matrix. */
  541.     IritFatalError("CombineClosedLoops: Inverse matrix does not exists");
  542.  
  543.     /* Evalaute the normal to the polygon (which must be convex!). Note we   */
  544.     /* cannt simply use the Plane normal as the polygon was transformed.     */
  545.     V = Pl -> PVertex;
  546.     do {
  547.     Vnext = V -> Pnext;
  548.     PT_SUB(V1, Vnext -> Coord, V -> Coord);
  549.     PT_SUB(V2, Vnext -> Pnext -> Coord, Vnext -> Coord);
  550.     GMVecCrossProd(PlNormal, V1, V2);
  551.     V = Vnext;
  552.     }
  553.     while (PT_LENGTH(PlNormal) < BOOL_EPSILON);
  554.  
  555.     PClosedTemp = PClosed;
  556.     while (PClosedTemp != NULL) {
  557.     /* Stage 2 - find MaxX extremum value of given loop, test the loop   */
  558.     /* direction, and reverse it if wrong. Note we convert the loop      */
  559.     /* given as InterSegListStruct list into IPVertexStruct list first.  */
  560.     PISegMaxX = PISeg = PClosedTemp -> PISeg;
  561.     MaxX = PISeg -> PtSeg[0][0];          /* Get first vertex X val. */
  562.     PISeg = PISeg -> Pnext;
  563.     while (PISeg)
  564.     {
  565.         if (PISeg -> PtSeg[0][0] > MaxX) {
  566.         MaxX = PISeg -> PtSeg[0][0];
  567.         PISegMaxX = PISeg;
  568.         }
  569.         PISeg = PISeg -> Pnext;
  570.     }
  571.     PClosedTemp -> PISegMaxX = PISegMaxX;
  572.  
  573.     PClosedTemp = PClosedTemp -> Pnext;
  574.     }
  575.  
  576.     /* Stage 3/4 - find the loop with biggest MaxX and combine it with the   */
  577.     /* polygon itself. Do it for all closed loops, in list:             */
  578.     while (PClosed != NULL) {
  579.     /* Find the one with maximum MaxX, and delete it from PClosed list.  */
  580.     PClosedLast = PClosedMaxX = PClosedTemp = PClosed;
  581.     MaxX = PClosedMaxX -> PISegMaxX -> PtSeg[0][0];
  582.     while (PClosedTemp != NULL)
  583.     {
  584.         if (PClosedTemp -> PISegMaxX -> PtSeg[0][0] > MaxX) {
  585.         PClosedMaxX = PClosedTemp;
  586.         PClosedMaxXLast = PClosedLast;
  587.         }
  588.         PClosedLast = PClosedTemp;
  589.         PClosedTemp = PClosedTemp -> Pnext;
  590.     }
  591.     if (PClosedMaxX == PClosed)
  592.         PClosed = PClosed -> Pnext;                    /* Del. from */
  593.     else
  594.         PClosedMaxXLast -> Pnext = PClosedMaxX -> Pnext; /* PClosed list.*/
  595.  
  596.     /* Create a vertex list from the loop: */
  597.     V = VHead = InterLoopToVrtxList(PClosedMaxX -> PISeg);
  598.     if (V -> Pnext == NULL || V -> Pnext -> Pnext == NULL)
  599.         IritFatalError("CombineClosedLoops: Closed loop with less than 3 vertices");
  600.  
  601.     V = VHead;
  602.     while (V -> Pnext -> Pnext != NULL)
  603.         V = V -> Pnext;                   /* Go to last pt. */
  604.     IPFreeVertex(V -> Pnext);        /* and free - same as first. */
  605.     V -> Pnext = VHead;               /* Make vertex list circular. */
  606.  
  607.     PISegMaxX = PClosedMaxX -> PISegMaxX;
  608.  
  609.     /* Now test if the vertex list should be reversed. Find the vertices */
  610.     /* which form the PISegMaxX segment, so V -> Pnext is the first      */
  611.         /* vertex in PISegMaxX segment. Then the 3 vertices V , V -> Pnext   */
  612.         /* (on PISegMaxX), V -> Pnext -> Pnext (on PISegMaxX), must form     */
  613.     /* convex corner which we use to test if loop needs to be reversed:  */
  614.     while (!BOOL_PT_APX_EQ(V -> Pnext -> Coord, PISegMaxX -> PtSeg[0]))
  615.             V = V -> Pnext;
  616.     VMaxX = V -> Pnext;
  617.  
  618.     /* Prepare in point in REAL position. */
  619.     PT_COPY(VStruct.Coord, V -> Coord);
  620.     MatMultVecby4by4(VStruct.Coord, VStruct.Coord, RotMat);
  621.     VStruct.Pnext = NULL;
  622.     if (TestAinB(&VStruct, PISegMaxX -> Pl, AinB)) {
  623.         /* The Inside of the object is actually the loop itself. In that */
  624.         /* case we simply return all the loops converted into polygon.   */
  625.         /* This case is simple...                         */
  626.         IPFreeVertexList(VHead);           /* Free loop vertex list. */
  627.         PClosedMaxX -> Pnext = PClosed;/* Put back first loop into list. */
  628.         PClosedTemp = PClosed = PClosedMaxX;
  629.         while (PClosedTemp != NULL) {    /* Transform the loops back. */
  630.         PISeg = PClosed -> PISeg;
  631.         while (PISeg != NULL) {
  632.             MatMultVecby4by4(PISeg -> PtSeg[0], PISeg -> PtSeg[0],
  633.                      RotMat);
  634.             MatMultVecby4by4(PISeg -> PtSeg[1], PISeg -> PtSeg[1],
  635.                      RotMat);
  636.  
  637.             PISeg = PISeg -> Pnext;
  638.         }
  639.         PClosedTemp = PClosedTemp -> Pnext;
  640.         }
  641.  
  642.         ClosedLoopsToPolys(PClosedMaxX, Pl);/* And convert them to polys.*/
  643.         return FALSE;       /* Boundary is NOT part of object result. */
  644.     }
  645.     PT_SUB(V1, VMaxX -> Coord, V -> Coord);
  646.     PT_SUB(V2, VMaxX -> Pnext -> Coord, VMaxX -> Coord);
  647.     GMVecCrossProd(Normal, V1, V2);
  648.     if (DOT_PROD(Normal, PlNormal) > 0) {        /* Need to reverse list. */
  649.         Vprev = VHead;
  650.         V = Vprev -> Pnext;
  651.         Vnext = V -> Pnext;
  652.         do {
  653.         V -> Pnext = Vprev;/* Reverse to point on prev instead next. */
  654.         Vprev = V;
  655.         V = Vnext;
  656.         Vnext = V -> Pnext;
  657.         }
  658.         while (Vprev != VHead);
  659.     }
  660.  
  661.     PISeg = PClosedMaxX -> PISeg;  /* Time to free the InterSegmentList: */
  662.     while (PISeg != NULL) {
  663.         PItemp = PISeg;
  664.         PISeg = PISeg -> Pnext;
  665.         IritFree((VoidPtr) PItemp);
  666.     }
  667.     IritFree((VoidPtr) PClosedMaxX);
  668.  
  669.     /* O.k. lets fire a ray from VMaxX to +X direction and see where it  */
  670.     /* intersects the polygon. The routine CutPolygonAtRay will add two  */
  671.     /* vertices at the ray intersection into polygon vertex list and     */
  672.     /* return a pointer to first one, so we can chain our loop directly  */
  673.     /* between these two new vertices.                     */
  674.     V = CutPolygonAtRay(Pl, VMaxX -> Coord);
  675.     Vnext = V -> Pnext;
  676.     /* Introduce a copy of VMaxX and successor to VMaxX: */
  677.     VMaxX -> Pnext = IPAllocVertex(VMaxX -> Count, VMaxX -> Tags, NULL,
  678.                                 VMaxX -> Pnext);
  679.     PT_COPY(VMaxX -> Pnext -> Coord, VMaxX -> Coord);
  680.     PT_CLEAR(VMaxX -> Pnext -> Normal);
  681.     V -> Pnext = VMaxX -> Pnext;
  682.     IP_SET_INTERNAL_VRTX(V);
  683.     VMaxX -> Pnext = Vnext;
  684.     IP_SET_INTERNAL_VRTX(VMaxX);
  685.     }
  686.  
  687.     /* Stage 5 - Time to rotate polygon back to its original position. */
  688.     V = VHead = Pl -> PVertex;
  689.     do {
  690.     MatMultVecby4by4(V -> Coord, V -> Coord, RotMat);
  691.     V = V -> Pnext;
  692.     }
  693.     while (V != NULL && V != VHead);
  694.  
  695.     SET_INOUTPUT_POLY(Pl);           /* Mark the polygon as in output. */
  696.     IP_RST_CONVEX_POLY(Pl);         /* This polygon is not convex any more. */
  697.  
  698.     return TRUE;
  699. }
  700.  
  701. /*****************************************************************************
  702. * DESCRIPTION:                                                               *
  703. *   Pushes on the adjacency stack, all adjacent polygons which are complete  *
  704. * (no intersection) and are adjacent to complete edges (originated from         *
  705. * input polygons) of the given polygon.                         *
  706. *                                                                            *
  707. * PARAMETERS:                                                                *
  708. *   Pl:           To be added to the adjacency stack.                        *
  709. *   AdjStack:     The adjacency stack to put Pl in.                          *
  710. *   StackPointer: Where exactly in the stack Pl is going to be pushed?       *
  711. *                                                                            *
  712. * RETURN VALUE:                                                              *
  713. *   void                                                                     *
  714. *****************************************************************************/
  715. static void PushAdjOnStack(IPPolygonStruct *Pl,
  716.                IPPolygonStruct *AdjStack[],
  717.                int *StackPointer)
  718. {
  719.     IPVertexStruct
  720.     *V = Pl -> PVertex;
  721.  
  722.     do {
  723.     if (V -> PAdj != NULL && BoolVerifyShareEdge(V, V -> PAdj))
  724.         AdjStack[++*StackPointer] = V -> PAdj;
  725.     if (*StackPointer >= ADJ_STACK_SIZE) {
  726.         IritFatalError("Adjacency stack overflow, object too big");
  727.     }
  728.     V = V -> Pnext;
  729.     }
  730.     while (V != Pl -> PVertex);
  731. }
  732.  
  733. /*****************************************************************************
  734. * DESCRIPTION:                                                               *
  735. *   Test if the edge [V - V->Pnext] is indeed on the boundary of Pl.         *
  736. *                                                                            *
  737. * PARAMETERS:                                                                *
  738. *   V:       First vertex of edge to verify.                                 *
  739. *   Pl:      Polygon to verify the edge shares its boundary.                 *
  740. *                                                                            *
  741. * RETURN VALUE:                                                              *
  742. *   int:     TRUE if [V - V->Pnext] is on Pl's boundary, FALSE otherwise.    *
  743. *****************************************************************************/
  744. int BoolVerifyShareEdge(IPVertexStruct *V, IPPolygonStruct *Pl)
  745. {
  746.     IPVertexStruct
  747.     *Vl = Pl -> PVertex;
  748.     VectorType Dir;
  749.     int InterNum = 0;
  750.     RealType InterVal[2], Dist;
  751.  
  752.     PT_SUB(Dir, V -> Pnext -> Coord, V -> Coord);
  753.     if ((Dist = PT_LENGTH(Dir)) == 0)
  754.         Dist = IRIT_EPSILON;
  755.  
  756.     do {
  757.     PointType Ptemp;
  758.  
  759.     CGPointFromPointLine(Vl -> Coord, V -> Coord, Dir, Ptemp);
  760.     if (CGDistPointPoint(Vl -> Coord, Ptemp) < IRIT_EPSILON) {
  761.         VectorType Dir2; 
  762.         RealType
  763.             Dist2 = CGDistPointPoint(V -> Coord, Ptemp);
  764.  
  765.         PT_SUB(Dir2, Ptemp, V -> Coord);
  766.         Dist2 = PT_LENGTH(Dir2);
  767.  
  768.         InterVal[InterNum] = Dist2 / Dist;
  769.         if (DOT_PROD(Dir2, Dir) < 0)
  770.         InterVal[InterNum] = -InterVal[InterNum];
  771.         if (++InterNum == 2) {
  772.         if (MIN(InterVal[0], InterVal[1]) < 1.0 &&
  773.             MAX(InterVal[0], InterVal[1]) > 0.0)
  774.             return TRUE;
  775.  
  776.         /* Save the second intersection as first one for next time. */
  777.         InterVal[0] = InterVal[1];
  778.         InterNum = 1;       
  779.         }
  780.     }
  781.     else
  782.         InterNum = 0;
  783.  
  784.     Vl = Vl -> Pnext;
  785.     }
  786.     while (Vl != Pl -> PVertex);
  787.  
  788.     return FALSE;
  789. }
  790.  
  791. /*****************************************************************************
  792. * DESCRIPTION:                                                               *
  793. *   Chains two polygonal lists into one. For fast processing it is prefered  *
  794. * that the first one is shorter. Returns pointer to chained list.         *
  795. *                                                                            *
  796. * PARAMETERS:                                                                *
  797. *   Pl1, Pl2:   The two polygonal objects to be chained together.            *
  798. *                                                                            *
  799. * RETURN VALUE:                                                              *
  800. *   IPPolygonStruct *: The combined/chained together polygonal list.         *
  801. *                                                                            *
  802. *                                                                            *
  803. *                                                                            *
  804. *****************************************************************************/
  805. static IPPolygonStruct *ChainPolyLists(IPPolygonStruct *Pl1,
  806.                        IPPolygonStruct *Pl2)
  807. {
  808.     IPPolygonStruct *Ptemp;
  809.  
  810.     if (Pl1 == NULL)
  811.         return Pl2;
  812.     else if (Pl2 == NULL)
  813.     return Pl1;
  814.     else {
  815.     Ptemp = Pl1;
  816.     while (Ptemp -> Pnext != NULL)
  817.         Ptemp = Ptemp -> Pnext;
  818.     Ptemp -> Pnext = Pl2;
  819.     return Pl1;
  820.     }
  821. }
  822.  
  823. /*****************************************************************************
  824. * DESCRIPTION:                                                               M
  825. *   This routine coordinates all the extraction of the polygons from the     M
  826. * intersecting lists. Does it in the following steps:                 M
  827. * 1. Mark all polygons with no intersection at all as complete polygons.     M
  828. *    (this is because this polygon will be totally in or out, according      M
  829. *    to inter-polygon adjacencies propagation...)                 M
  830. *    Also mark them as undefined (if in output or undefined) yet.         M
  831. *    Uses IPPolygonStruct Tags to save these bits.                 M
  832. * 2. do                                         M
  833. *    2.1. Convert the unordered segment list of each polygon to closed loops M
  834. *         (if create a hole in polygon) or open (if crosses its boundary).   M
  835. *    2.2. Order the open loops along the perimeter of the polygon (note      M
  836. *      these loops cannt intersect. For example (5 vertices polygon):     M
  837. *             -----------------------------L3                 V
  838. *        |  ---------------L1  -----L2 |          --------L4   --L5   V
  839. *        | |               |  |     |  |         |        |   |  |    V
  840. *      P0 ------ P1 ------- P2 ----- P3 -------- P4 ------ P5 -------- P0 V
  841. *         Note L1, L2 are enclosed in L3 loop, and that the order is         M
  842. *         circular.                                 M
  843. *    2.3. "Break" the polygon at each open loop that has no enclosed loops   M
  844. *      in it. For example we can start at L1, L2, L4, L5 and then L3.     M
  845. *      "Break" means - replace the vertex chain between the two loop end  M
  846. *      points, with the loops itself. Depends upon the relation required  M
  847. *      we may need to output a new polygon form from the deleted chain    M
  848. *      and that loop. In addition we may form a new polygon from last     M
  849. *      loop and was was left from the original polygon             M
  850. *      For each formed polygon, for each complete edge of it (i.e. edge   M
  851. *      which was originally in the polygon) test the adjacent polygon     M
  852. *      if it is complete (as marked in 1.) and if in or undefined (marked M
  853. *      undefined in 1.) is still undefined:                     M
  854. *      2.3.1. set it to be in.                         M
  855. *      2.3.2. push it on adjacency stack.                     M
  856. *    2.4. For each closed loop - find in which polygon (from polygons         M
  857. *      created in 2.3.) it is enclosed, and decompose it.             M
  858. * 3. While adjacencies stack not empty do:                     M
  859. *    3.1. pop top polygon from stack and output it.                 M
  860. *    3.2. For each of its edges (which obviousely must be complete edges)    M
  861. *      if adjacent polygon is complete and undefined:             M
  862. *      3.3.1. set it to be in.                         M
  863. *      3.3.2. push it on adjacency stack.                     M
  864. *    3.3  go back to 3.                                 M
  865. *                                         M
  866. *   The above algorithm defines in as in output, but dont be confused with   M
  867. * the required inter-object AinB (or AoutB if FALSE), which used to         M
  868. * determine which side of the trimming loop should be output.             M
  869. *   Note this routine may return non-convex polygons (but marked as so) even M
  870. * though the input for the booleans must be convex polygons only!         M
  871. *   In order to keep the given object unchanged, a whole new copy off the    M
  872. * polygon list is made. The polygons of the list that are not in the output  M
  873. * are freed: a global list of all polygons (pointers) is used to scan them   M
  874. * in the end and free the unused ones (list PolysPtr).                 M
  875. *                                                                            *
  876. * PARAMETERS:                                                                M
  877. *   PObj:    Object that need to be rebuilt according to the intersection    M
  878. *            curves that were found, both closed and open loops.             M
  879. *   AinB:    Type of inclusion/exclusion requested.                          M
  880. *                                                                            *
  881. * RETURN VALUE:                                                              M
  882. *   IPObjectStruct *: The newly created clipped object.                      M
  883. *                                                                            *
  884. * KEYWORDS:                                                                  M
  885. *   BoolExtractPolygons, Booleans                                            M
  886. *****************************************************************************/
  887. IPObjectStruct *BoolExtractPolygons(IPObjectStruct *PObj, int AinB)
  888. {
  889.     int NumOfPolys = 0,
  890.     StackPointer = -1;
  891.     IPPolygonStruct *AdjStack[ADJ_STACK_SIZE], **PolysPtr, *OriginalPl,
  892.         *Pl, *PlHead, *PlNext, *OutputPl = NULL, *SplPl, *NewPl;
  893.     IPVertexStruct *V, *Vnext;
  894.     InterSegListStruct *PClosed, *POpen, *Ptemp;
  895.  
  896. #ifdef DEBUG3
  897.     printf("Enter BoolExtractPolygons\n");
  898. #endif /* DEBUG3 */
  899.  
  900.     /* Stage 1. - mark all polygons as needed: */
  901.     PlHead = Pl = PObj -> U.Pl;
  902.     /* Gen. a copy of Pl, so we can modify the original polygon list: */
  903.     PObj -> U.Pl = CopyPolygonList(Pl);
  904.  
  905.     while (Pl != NULL) {
  906.     NumOfPolys++;         /* Count number of polygons in original object. */
  907.     if (Pl -> PAux != NULL) {     /* The intersection list is not empty! */
  908.         RST_COMPLETE_POLY(Pl);     /* Mark it as non complete polygon. */
  909.         V = Pl -> PVertex;
  910.         do {
  911.         SET_ORIGINAL_VRTX(V); /* Mark vertices from original object. */
  912.         V = V -> Pnext;
  913.         }
  914.         while (V != Pl -> PVertex);
  915.     }
  916.     else {
  917.         SET_COMPLETE_POLY(Pl);         /* Mark it as complete polygon. */
  918.         RST_INOUTPUT_POLY(Pl);     /* And as undefined (if in output). */
  919.         RST_ADJPUSHED_POLY(Pl);     /* And as not pushed on adj. stack. */
  920.     }
  921.     Pl = Pl -> Pnext;
  922.     }
  923.  
  924.     /* Stage 2. - scan the polygons and subdivide the intersecting ones: */
  925.     Pl = PlHead;
  926.  
  927.     /* We will save pointers to ALL polygons in list so we could free in the */
  928.     /* end the ones that are not in the output list, and therefore unused.   */
  929.     PolysPtr = (IPPolygonStruct **)
  930.         IritMalloc(sizeof(IPPolygonStruct *) * NumOfPolys);
  931.     NumOfPolys = 0;
  932.  
  933.     while (Pl != NULL) {
  934.     PolysPtr[NumOfPolys++] = Pl;        /* Save pointer to this polygon. */
  935.  
  936.     PlNext = Pl -> Pnext;
  937.     Pl -> Pnext = NULL;
  938.  
  939.     if (!IS_COMPLETE_POLY(Pl)) {/* They are intersections with this one. */
  940.         /* Convert the intersecting segments into open/closed loops. */
  941.         BoolLoopsFromInterList(Pl, &PClosed, &POpen);
  942.  
  943.         /* Save copy of original polygon vertex list as we need its      */
  944.         /* normals to interpolate for the internal ones.             */
  945.         OriginalPl = IPAllocPolygon(1, Pl -> Tags,
  946.                     CopyVertexList(Pl -> PVertex), NULL);
  947.         IP_RST_BBOX_POLY(OriginalPl);
  948.         PLANE_COPY(OriginalPl -> Plane, Pl -> Plane);
  949.  
  950.         if (POpen != NULL) {
  951.         /* Sort the Open loops into an order we can handle... */
  952.         BoolSortOpenInterList(Pl, &POpen);
  953.         SplPl = NewPl = NULL;     /* Keep the list of split polygons. */
  954.  
  955.         while (POpen != NULL) {    /* Clip the open loops from polygon: */
  956.             /* Note ClipOpenLoopFromPoly also frees the InterSegment */
  957.             /* list pointed by POpen (but not POpen itself).          */
  958.             NewPl = ClipOpenLoopFromPoly(Pl, POpen, AinB);
  959.             if (NewPl != NULL) {   /* If loop clipped a new polygon, */
  960.             PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane);
  961.             NewPl -> Pnext = SplPl;/* add to split polygon list. */
  962.             SplPl = NewPl;
  963.             /* And push adj. polygons of complete edges on stack.*/
  964.             PushAdjOnStack(NewPl, AdjStack, &StackPointer);
  965.             }
  966.             Ptemp = POpen;
  967.             POpen = POpen -> Pnext;
  968.             IritFree((VoidPtr) Ptemp);
  969.         }
  970.  
  971.         /* Last clip generated nothing (NewPl == NULL) so part that  */
  972.         /* left from Pl (PlCopy) is IN output list! Add this poly:   */
  973.         if (NewPl == NULL) {
  974.             PLANE_COPY(Pl -> Plane, OriginalPl -> Plane);
  975.             Pl -> Pnext = SplPl; /* And chain what was left from it. */
  976.             SplPl = Pl;
  977.             /* And push adjacent polygons of complete edges on stack.*/
  978.             PushAdjOnStack(Pl, AdjStack, &StackPointer);
  979.             SET_INOUTPUT_POLY(Pl);/* So we wouldnt free that in end. */
  980.             IP_RST_CONVEX_POLY(Pl);       /* May be not convex now. */
  981.         }
  982.  
  983.         UpdateVerticesNormals(SplPl, OriginalPl);
  984.         }
  985.         else
  986.         SplPl = Pl;
  987.  
  988.         if (PClosed != NULL) {
  989.         for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext)
  990.             Pl -> PAux = NULL;
  991.  
  992.         /* Classify the closed loops into the appropriate polygon. */
  993.         while (PClosed != NULL) {
  994.             Ptemp = PClosed -> Pnext;
  995.             for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) {
  996.             if (CGPolygonRayInter3D(Pl, PClosed -> PISeg -> PtSeg[0],
  997.                         0) % 2 == 1) {
  998.                 /* This closed loop is contained in this polygon.*/
  999.                 PClosed -> Pnext = (InterSegListStruct *) Pl -> PAux;
  1000.                 Pl -> PAux = (VoidPtr) PClosed;
  1001.                 break;
  1002.             }
  1003.             }
  1004.             if (Pl == NULL) {
  1005.             /* This closed loop is part of a trimmed out by open */
  1006.             /* loop region. It should be only the island formed  */
  1007.             /* by this closed loop then.                 */
  1008.             /* Make a new polygon - a copy of the original and   */
  1009.             /* Put this loop in it.                     */
  1010.             NewPl = IPAllocPolygon(1, OriginalPl -> Tags,
  1011.                 CopyVertexList(OriginalPl -> PVertex), NULL);
  1012.             IP_RST_BBOX_POLY(NewPl);
  1013.             PLANE_COPY(NewPl -> Plane, OriginalPl -> Plane);
  1014.             NewPl -> PAux = (VoidPtr) PClosed;
  1015.             NewPl -> Pnext = SplPl;
  1016.             SplPl = NewPl;
  1017.             }
  1018.             PClosed = Ptemp;
  1019.         }
  1020.  
  1021.         for (Pl = SplPl; Pl != NULL; Pl = Pl -> Pnext) {
  1022.             /* Make a "cut" from the loop(s)  +-------+    +-------+ */
  1023.             /* to boundary if possible, and   |       |    |       | */
  1024.             /* converting Pl to a nonconvex   |  / \  | -> |  / \__| */
  1025.             /* polygon, that has an edge (the |  \ /  | -> |  \ /  | */
  1026.             /* cut) which is shared twice in  |       |    |       | */
  1027.             /* the same polygon              +-------+    +-------+ */
  1028.             PClosed = (InterSegListStruct *) Pl -> PAux;
  1029.             Pl -> PAux = NULL;
  1030.             if (CombineClosedLoops(Pl, PClosed, AinB)) {
  1031.             /* If returned with TRUE -  polygon boundary is in   */
  1032.             /* output, so add all its neighbours to adj. stack.  */
  1033.             PushAdjOnStack(Pl, AdjStack, &StackPointer);
  1034.             }
  1035.  
  1036.             UpdateVerticesNormals(Pl, OriginalPl);
  1037.         }
  1038.         }
  1039.  
  1040.         OutputPl = ChainPolyLists(SplPl, OutputPl);
  1041.  
  1042.         /* Free the original polygon vertex list. */
  1043.         IPFreePolygon(OriginalPl);
  1044.     }
  1045.  
  1046.     Pl = PlNext;
  1047.     }
  1048.  
  1049.     /* Stage 3. - handling adjacencies and propagate them in polygons:         */
  1050.     /* Pop off the elements from the stack, and propagate them using their   */
  1051.     /* adjacencies.                                 */
  1052.     while (StackPointer >= 0) {
  1053.     Pl = AdjStack[StackPointer--];             /* Pop top element. */
  1054.     if (!IS_COMPLETE_POLY(Pl) ||        /* Ignore non complete polygons. */
  1055.          IS_INOUTPUT_POLY(Pl))
  1056.         continue;                  /* If already handled. */
  1057.  
  1058.     SET_INOUTPUT_POLY(Pl);      /* Mark this one as handled for next time. */
  1059.  
  1060.     V = Pl -> PVertex;   /* Push all adjacent ones that not handled yet. */
  1061.     do {
  1062.         if (V -> PAdj &&
  1063.         IS_COMPLETE_POLY(V -> PAdj) &&
  1064.         !IS_INOUTPUT_POLY(V -> PAdj) &&
  1065.         !IS_ADJPUSHED_POLY(V -> PAdj)) {
  1066.         SET_ADJPUSHED_POLY(V -> PAdj);
  1067.         AdjStack[++StackPointer] = V -> PAdj;   /* Push it on stack. */
  1068.         if (StackPointer >= ADJ_STACK_SIZE)
  1069.             IritFatalError("Adjacency stack overflow, object too big");
  1070.         }
  1071.         V = V -> Pnext;
  1072.     }
  1073.     while (V != Pl -> PVertex);
  1074.  
  1075.     Pl -> Pnext = OutputPl;           /* And chain it into output list. */
  1076.     OutputPl = Pl;
  1077.     }
  1078.  
  1079.     /* Free all polygons which are not in the output list: */
  1080.     while (--NumOfPolys >= 0) {
  1081.     if (!IS_INOUTPUT_POLY(PolysPtr[NumOfPolys])) {
  1082.         IPFreePolygon(PolysPtr[NumOfPolys]);
  1083.     }
  1084.     }
  1085.     IritFree((VoidPtr) PolysPtr);
  1086.  
  1087.     /* Another floating point kludge: a polygon may have zero length edge so */
  1088.     /* search for those and remove them - someone may die because of one...  */
  1089.     Pl = OutputPl;
  1090.     while (Pl != NULL) {
  1091.     V = Pl -> PVertex;
  1092.     do {
  1093.         Vnext = V -> Pnext;
  1094.         if (BOOL_PT_APX_EQ(V -> Coord, Vnext -> Coord)) {
  1095.         /* Ahh - we got you. Simply skip Vnext vertex and free it: */
  1096.         V -> Pnext = Vnext -> Pnext;
  1097.         /* Update polygon vertex pointer if point on freed vertex: */
  1098.         if (Pl -> PVertex == Vnext)
  1099.             Pl -> PVertex = Vnext -> Pnext;
  1100.         IPFreeVertex(Vnext);
  1101.         Vnext = V -> Pnext;
  1102.         }
  1103.         V = Vnext;
  1104.     }
  1105.     while (V != Pl -> PVertex && V != NULL);
  1106.  
  1107.     Pl = Pl -> Pnext;
  1108.     }
  1109.  
  1110. #ifdef DEBUG3
  1111.     printf("Exit BoolExtractPolygons\n");
  1112. #endif /* DEBUG3 */
  1113.  
  1114.     return GenPolyObject("", OutputPl, NULL);     /* Return resulting object. */
  1115. }
  1116.  
  1117. #ifdef DEBUG
  1118.  
  1119. /*****************************************************************************
  1120. * DESCRIPTION:                                                               *
  1121. *   Print the content of the given vertex list, to standard output.         *
  1122. *                                                                            *
  1123. * PARAMETERS:                                                                *
  1124. *   V:       The vertex list to be printed.                                  *
  1125. *                                                                            *
  1126. * RETURN VALUE:                                                              *
  1127. *   void                                                                     *
  1128. *****************************************************************************/
  1129. void BoolPrintVrtxList(IPVertexStruct *V)
  1130. {
  1131.     IPVertexStruct
  1132.     *VHead = V;
  1133.  
  1134.     do {
  1135.     printf("    %12lf %12lf %12lf",
  1136.            V -> Coord[0], V -> Coord[1], V -> Coord[2]);
  1137.     if (IP_IS_INTERNAL_VRTX(V))
  1138.         printf(" (Internal)\n");
  1139.     else
  1140.         printf("\n");
  1141.     V = V -> Pnext;
  1142.     }
  1143.     while (V!= NULL && V != VHead);
  1144. }
  1145.  
  1146. /*****************************************************************************
  1147. * DESCRIPTION:                                                               *
  1148. *   Print the content of the given InterSegment list, to standard output.    *
  1149. *                                                                            *
  1150. * PARAMETERS:                                                                *
  1151. *   PInt:       The InterSegment list to be printed.                         *
  1152. *                                                                            *
  1153. * RETURN VALUE:                                                              *
  1154. *   void                                                                     *
  1155. *****************************************************************************/
  1156. void BoolPrintInterList(InterSegmentStruct *PInt)
  1157. {
  1158.     printf("INTER SEGMENT LIST:\n");
  1159.  
  1160.     if (PInt)
  1161.     printf("Entry vertex pointer %p\n", PInt -> V[0]);
  1162.     while (PInt) {
  1163.     printf("%9lg %9lg %9lg (%04ld), %9lg %9lg %9lg (%04ld)\n",
  1164.         PInt -> PtSeg[0][0], PInt -> PtSeg[0][1], PInt -> PtSeg[0][2],
  1165.         PInt -> V[0],
  1166.         PInt -> PtSeg[1][0], PInt -> PtSeg[1][1], PInt -> PtSeg[1][2],
  1167.         PInt -> V[1]);
  1168.     if (PInt -> Pnext == NULL)
  1169.         printf("Exit vertex pointer %p\n", PInt -> V[1]);
  1170.  
  1171.     PInt = PInt -> Pnext;
  1172.     }
  1173. }
  1174.  
  1175. #endif /* DEBUG */
  1176.